#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;
class Solution
{
public:
    int cnt = 0;
    bool visited[100][100] = {false};
    int dis[4][2] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
    int caldigitsum(int x)
    {
        int sum = 0;
        while (x != 0)
        {
            sum += x % 10;
            x /= 10;
        }
        return sum;
    }
    bool canget(int x, int y, int k)
    {
        return (caldigitsum(x) + caldigitsum(y)) <= k;
    }
    void dfs(int curi, int curj, int k, int m, int n)
    {
        if (visited[curi][curj] == true)
            return;
        cnt++;
        visited[curi][curj] = true;
        int x, y;
        for (int i = 0; i < 4; ++i)
        {
            x = curi + dis[i][0];
            y = curj + dis[i][1];
            if (x < 0 || x >= m || y < 0 || y >= n)
                continue;
            if (canget(x, y, k))
            {
                dfs(x, y, k, m, n);
            }
        }
    }
    int movingCount(int m, int n, int k)
    {
        memset(visited, false, sizeof(visited));
        dfs(0, 0, k, m, n);
        return cnt;
    }
};